package Lab02.Q10;

import java.util.Arrays;
import java.util.Scanner;

public class quickSort2 {
    public static void main(String[] args) {
        int arr[] = {12, 45, 67, 89, 123, -45, 67};
        //System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("请输入要查询的数字(整数):");
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        for (int i = 0; i < arr.length; i++) {
            if (num == arr[i]) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }

    public static void sort(int[] arr) {
        if (arr.length > 0) {
            sort(arr, 0, arr.length - 1);
        }
    }

    public static int[] sort(int[] arr, int low, int high) {
        int i = low, j = high;
        if (i > j)
            return null;
        int k = arr[i];
        while (i < j) {//哨兵移动
            while (i < j && arr[j] >= k)
                j--;
            while (i < j && arr[i] < k)
                i++;
            if (i < j) {
                int swap = arr[i];
                arr[i] = arr[j];
                arr[j] = swap;
            }
            k = arr[i];
            arr[i] = arr[low];
            arr[low] = k;
            sort(arr, low, i - 1);
            sort(arr, i + 1, high);
        }
        return arr;
    }
}
